A.1 Dataset statistics In Table 5, we provided the statistics of all datasets used in our experiments. We run all experiments on a machine with 80 Intel(R) Xeon(R) E5-2698 v4 @ 2.20GHz CPUs, and Our implementations are based on Python 3.8.10, Curves in all three plots are the higher the better. All three metrics are the higher the better. GStarX outperforms the other methods A.5 Detailed entropy-based sparsity evaluation In Section 5.2 we study whether the obtained scores by GStarX are sparse and follow [ We now provide a more detailed discussion of this study.

The Shapley value is a prominent tool for interpreting black-box machine learning models thanks to its strong theoretical foundation. However, for models with structured inputs, such as graph neural networks, existing Shapley-based explainability approaches either focus solely on node-wise importance or neglect the graph structure when perturbing the input instance. This paper introduces the Myerson-Taylor interaction index that internalizes the graph structure into attributing the node values and the interaction values among nodes. Unlike the Shapley-based methods, the Myerson-Taylor index decomposes coalitions into components satisfying a pre-chosen connectivity criterion. We prove that the Myerson-Taylor index is the unique one that satisfies a system of five natural axioms accounting for graph structure and high-order interaction among nodes. Leveraging these properties, we propose Myerson-Taylor Structure-Aware Graph Explainer (MAGE), a novel explainer that uses the second-order Myerson-Taylor index to identify the most important motifs influencing the model prediction, both positively and negatively. Extensive experiments on various graph datasets and models demonstrate that our method consistently provides superior subgraph explanations compared to state-of-the-art methods.

Explaining machine learning models is an important and increasingly popular area of research interest. The Shapley value from game theory has been proposed as a prime approach to compute feature importance towards model predictions on images, text, tabular data, and recently graph neural networks (GNNs) on graphs. In this work, we revisit the appropriateness of the Shapley value for GNN explanation, where the task is to identify the most important subgraph and constituent nodes for GNN predictions. We claim that the Shapley value is a non-ideal choice for graph data because it is by definition not structure-aware. We propose a Graph Structure-aware eXplanation (GStarX) method to leverage the critical graph structure information to improve the explanation. Specifically, we define a scoring function based on a new structure-aware value from the cooperative game theory proposed by Hamiache and Navarro (HN). When used to score node importance, the HN value utilizes graph structures to attribute cooperation surplus between neighbor nodes, resembling message passing in GNNs, so that node importance scores reflect not only the node feature importance, but also the node structural roles. We demonstrate that GStarX produces qualitatively more intuitive explanations, and quantitatively improves explanation fidelity over strong baselines on chemical graph property prediction and text graph sentiment classification.

While Shapley's analysis was originally thought to quantify the worth of human agents in a team, Research in the field of Multi-Agent Systems (MAS) suggests its application is straightforward to every other possible transferable viable pathways to solve complex tasks [1]. In a MAS utility coalitional game that respects the needed mathematical environment, every agent is, in principle, an individual independent properties. of one another with its own characteristics and skills. The field of possible applications of Shapley and Myerson The main idea is that by assigning to each agent a specific subtask analyses or their generalizations is broad. Shapley analysis or according to its perks and hence exploiting a delocalized its suitable generalizations can be applied for instance to estimate control, it is possible to solve a problem more efficiently. The the contributions of basketball players in a match using the human society itself is an example of a MAS since groups of recorded match data and statistics [3]. If the practitioner possesses individuals usually train according to their nature to exercise some information about the connectivity of interactions, specific professions that require different expertise: medical or, e.g., spatial rules of the game that restrict the interaction personnel, firefighters, engineers, etc. When analyzing the behavior among agents, Shapley and Myerson analyses can be used to of agents in a MAS a question arises immediately: according assess the importance of vertices, i.e., agents, in graphs. Recent to a common goal to be reached, which agent is contributing works investigated the Shapley and Myerson analyses of the most, and which are its most important individual transportation networks [4] and bus-holding strategies [5].

We study instancewise feature importance scoring as a method for model interpretation. Any such method yields, for each predicted instance, a vector of importance scores associated with the feature vector. Methods based on the Shapley score have been proposed as a fair way of computing feature attributions of this kind, but incur an exponential complexity in the number of features. This combinatorial explosion arises from the definition of the Shapley value and prevents these methods from being scalable to large data sets and complex models. We focus on settings in which the data have a graph structure, and the contribution of features to the target variable is well-approximated by a graph-structured factorization. In such settings, we develop two algorithms with linear complexity for instancewise feature importance scoring. We establish the relationship of our methods to the Shapley value and another closely related concept known as the Myerson value from cooperative game theory. We demonstrate on both language and image data that our algorithms compare favorably with other methods for model interpretation.